This application is based on an application No. 10-043230 filed in Japan, the content of which is hereby incorporated by reference.
(1) Field of the Invention
The present invention relates to a device authentication and encrypted communication system. Secure data communication takes place between one of a plurality of user devices and a system device, after each device has confirmed the legitimacy of the other.
(2) Description of the Related Art
Generally speaking, ensuring the security of valuable data during data communication is a serious problem. When transferring such data, it is essential to confirm that the receiver device is legitimate. In addition, the data needs to be protected from interception or tampering by a third party while being sent on communication paths.
A typical example of the kind of data communication system that attaches great importance to ensuring security is an automatic highway toll collecting system using radio communication.
Automatic Highway Toll Collecting System
The following is an explanation of a hypothetical automatic highway toll collecting system based on current thinking.
In this automatic highway toll collecting system, payment of highway usage charges, or tolls, is made by radio communication between an onboard device installed in a vehicle and roadside devices located at each highway entrance and exit toll gate.
The onboard device uses a removable IC (Integrated Circuit) card. This functions as a prepaid card, on which balance information showing a certain sum of money is recorded.
At a highway entrance gate (hereinafter referred to as an entrance gate) an onboard device transmits an onboard device ID to a roadside device by radio. The roadside device then sends entrance information, including a gate ID, entrance time and the like, to the onboard device. The onboard device receives the entrance information from the roadside device and records it on the IC card.
Conversely, at a highway exit gate (hereinafter referred to as an exit gate) an onboard device transmits entrance information and balance information to a roadside device by radio. The roadside device then calculates the highway toll based on the received entrance information, subtracts the toll from the received balance information and updates the balance information. The updated balance information is then transmitted to the onboard device by radio.
It should be noted that the automatic highway toll collecting system is assumed to contain several million cars and several thousand roadside devices. Furthermore, radio communication between onboard devices and roadside devices is possible over a range of several tens of meters, so that vehicles having an onboard device do not need to stop at entrance or exit gates in order to pay tolls or similar. As a result, traffic congestion in the vicinity of such gates can be reduced.
This kind of automatic highway toll payment system would naturally need to achieve error-free high speed communication in order to operate successfully. However, the following security issues also need to be resolved.
Firstly, a roadside device must confirm that an onboard device is legitimate. A roadside device needs to recognize immediately that a communication from a bogus onboard device is fake, so that countermeasures, such as barring the gate or recording the numberplate of the offending vehicle while photographing the driver, can be taken.
On the other hand, the onboard device also needs to confirm that the roadside device is legitimate. Attempts to make illegal profit, occurring when a bogus roadside device communicates with an onboard device, need to be prevented One example of such an attempt is altering the entrance information recorded inside the IC card, so that the toll paid is for a shorter distance than the actual distance traveled.
Furthermore, the content of radio communication between an onboard device and a roadside device must not be vulnerable to interception and misuse by a third party.
Ensuring Data Communication Security by Using Shared Secret Information
The above-mentioned security issues can be resolved by using widely-known device authentication and encrypted communication techniques when performing data transfer by radio between an onboard device and a roadside device.
For example, a certain secret key encryption algorithm and certain secret information may be shared between the onboard device and the roadside device. This secret information is conventionally known as an encryption key or a decryption key. If the secret key encryption algorithm and the secret information are shared between the onboard device and the roadside device, they can be used to perform mutual device authentication, to encrypt data before transmission and to decrypt data after reception.
Here, encryption and decryption based on a secret key encryption algorithm requires a comparatively smaller computational ability than a public key encryption algorithm, making high-speed processing possible. As a result, encrypted communication based on a secret key encryption algorithm is effective in an automatic highway toll collecting system that collects tolls automatically without requiring vehicles to stop.
However, since the automatic highway toll collecting system described above has a plurality of onboard devices, each must be provided with unique secret information. The reason for this is as follows, Assume that an onboard device A and an onboard device B have the same secret information. Should a third party somehow manage to obtain the secret information of onboard device A and use it to produce a bogus onboard device Axe2x80x2, attempts to exclude bogus onboard device Axe2x80x2 from the system by using a list will result in the simultaneous exclusion of the legitimate onboard device B.
Problems
Here, if the secret information differs for each onboard device, the question of how a roadside device is to obtain the secret information of every onboard device becomes a problem.
One possible method is to store information corresponding to the IDs and secret information of all of the onboard devices in advance in the roadside devices. However, if this method is used, updating the storage content of the several thousand roadside devices existing in the system is extremely troublesome. Also, the method has a weakness in that the secret information in all of the onboard devices will be exposed in the event of one of the roadside devices being analyzed by a third party.
Another method involves deriving the secret information for an onboard device from a secret function f in the onboard device ID. The value of this function f (ID) is recorded in the onboard device, and the roadside device possesses the same function, so that a method in which the roadside device receives notice of the onboard device ID, from which it then derives the secret information, can be envisaged. However, this method has a drawback in that, if a roadside devices is analyzed by a third party, the function f will be exposed, which results in the secret information in all of the onboard devices being compromised.
It should be noted that these problems are not peculiar to an automatic highway toll collecting system. Similar problems will also be apparent in any system in which the need to ensure security of data communication between one of a plurality of user devices and one of a plurality of system devices produces a system that requires secret data to be shared between user devices and system devices.
The present invention is designed to overcome the above problems, and relates to device authentication and encrypted communication occurring between a user device and a system device. The first objective or the invention is to provide a device authentication and encrypted communication system having a security function which maintains a high security level for communication even when illegal intrusion and analysis threaten the system device. Furthermore, when this kind of device authentication and encrypted communication uses encryption and decryption based on a secret key encryption algorithm, the second objective of the invention is to provide a key delivery method that delivers the key so as to prevent illegal intrusion and analysis of the system device.
A device authentication and encrypted communication system which achieves the above mentioned first objective is one comprising a plurality of user devices, a system device, and a control device, where device authentication and encrypted communication are performed between the plurality of user devices and the system device. Each of the plurality of user devices stores a piece of secret information that is unique to the user device. The control device produces pieces of key capsule data by performing a specified conversion on pieces of secret information of the plurality of user devices, provides each user device with a piece of key capsule data that has been produced from the piece of secret information stored in the user device, and provides the system device with a specified key that enables the system device to obtain pieces of secret information of user devices from pieces of key capsule data provided by the user devices. Then the user device transmits the piece of key capsule data received from the control device to the system device and the system device recovers the piece of secret information stored in the user device from the piece of key capsule data received from the user device using the specified key. During device authentication and encrypted communication between one of the user devices and the system device, the user device and the system device perform one of encryption and decryption according to a secret key encryption algorithm, using the piece of secret information that is unique to the user device as a key. The term xe2x80x9ckey capsule dataxe2x80x9d is equivalent to xe2x80x9cencrypted keyxe2x80x9d. The term symmetric is characteristic of a shared key encrypted communication system. The term asymmetric is characteristic of a public/private key system where the private key is not disclosed to another party.
Using this construction, a system device recovers unique secret information, which is different for each user device, from the key capsule data transmitted from a user device. As a result, device authentication and encrypted communication can take place with the user device without storing unique secret information and linked user device IDs for all of the user devices. Accordingly, the system device does not need to record unique secret information for all of the user devices. Therefore, even if an ill-intentioned third party manages to illegally invade and analyze the system device, they will not be able to obtain the unique secret information of the user devices.
Furthermore, in the device authentication and encrypted communication system, the control device stores, in advance, a signing key used in a digital signature conversion with message recovery method, and a corresponding verification key. The specified conversion is a digital signature conversion with message recovery made using the signing key. The specified key is the verification key. The system device obtains a piece of secret information from a piece of key capsule data, by performing a digital signature verification conversion with message recovery corresponding to the digital signature conversion with message recovery, using the specified key.
In the above construction, key capsule data is produced by a digital signature conversion with message recovery. As a result, even if the verification key, used for a signature verification conversion in this digital signature conversion with message recovery, is obtained from the system device by illegal intrusion or analysis, the signing key used in the signature conversion with message recovery cannot be derived from this verification key. Therefore, key capsule data cannot be forged by an ill-intentioned third party.
Furthermore, in the device authentication and encrypted communication system, device authentication is performed between one of the user devices and the system device, where one of the user device and the system device is a first device and another is a second device. The following procedures are used. The first device encrypts random data using the secret key encryption algorithm and sends the encrypted random data to the second device. The second device then receives the encrypted random data, decrypts the encrypted random data using the secret key encryption algorithm to produce response data, and sends the response data to the first device. The first device receives the response data and compares the response data with the random data.
Using the above construction, a system device shares unique secret information recovered from key capsule data with a user device. As a result, authentication of the legitimacy of a user device or a system device takes place using a challenge-response procedure based on a secret key encryption algorithm, which uses this unique secret information as a shared key. If authentication is successful, this confirms that the unique secret information has been correctly shared. Furthermore, if it is assumed, as mentioned above, that forgery of key capsule data by ill-intentioned persons is impossible, authentication which uses a challenge-response procedure to confirm the legitimacy of a user device has a high level of accuracy.
Furthermore, in the device authentication and encrypted communication system, the digital signature conversion with message recovery and the digital signature verification conversion with message recovery are based on elliptic curve theory.
In the above construction, the sharing of unique secret information allows the quantity of key capsule data transmitted from a user device to a system device can be reduced without lowering the security level of the system.
Furthermore, in the device authentication and encrypted communication system, the user device is an onboard device, installed in a vehicle and the system device is a roadside device, placed near a road. Data communication between the user device and the system device takes place when the user device passes in a vicinity of the system device.
Using the above construction, when one of a plurality of vehicles in which an onboard device is installed passes in the vicinity of a roadside device placed by a road, a secret key, the security of which is preserved, can be shared between the onboard device and the roadside device. Accordingly, device authentication and encrypted communication can take place between the onboard device and the roadside device using a secret key encryption algorithm for encryption and decryption. This takes place relatively faster than device authentication and encryption communication using a public key encryption algorithm, so traffic congestion occurring in the vicinity of the place where the roadside device is situated can be prevented.
Furthermore, in the device authentication and encrypted communication system, device authentication is a process in which the user device and the system device authenticate each other. In addition, encrypted communication between the user device and the system device takes place bidirectionally.
Using the above construction, the system device can confirm that the user device is a legitimate device, which has received key capsule data from a control center, and the user device can confirm that the system device is a legitimate device, which has received the verification key from the control center. In addition, data can be transmitted and received securely via a public communication channel.
Furthermore, in the device authentication and encrypted communication system each piece of secret information stored by each user device has been distributed by the control unit.
Using the above construction, the control center can produce key capsule data by performing a signature conversion with message recovery on unique secret information, before distributing the unique secret information to a user device. As a result, it is not necessary to provide the control center with a means for receiving unique secret information from a user device and a simple construction can be achieved.
Furthermore, in the device authentication and encrypted communication system, the control unit stores, in advance, a public key used in a public key encryption method, and a corresponding secret key. The specified conversion is a public key encryption conversion made using the public key and the specified key is the secret key. The system device obtains a piece of secret information from a piece of key capsule data by performing a decryption conversion corresponding to the public key encryption conversion, using the specified key.
Using the above construction, a system device can recover unique secret information using a secret key distributed from the control center. Therefore, it is not necessary to store unique secret information in all of the user devices in advance. If the unique secret information is not stored in advance, the unique secret information of all of the user devices cannot be exposed, even if a system device is illegally invaded and analyzed. As a result, the security level of the system is increased.
Furthermore, in a key distribution method, which achieves the second objective above, one out of a plurality of user devices, each of which stores different secret information, distributes secret information to a system device as a key to be used in device authentication and encrypted communication. The key distribution method comprises of the following steps. In a key capsule data production and distribution step, key capsule data is produced, by performing a digital signature conversion with message recovery on the unique secret information in each user device, and distributed to each user device. In a verification key distribution step, a verification key, used in a digital signature verification conversion with message recovery corresponding to the digital signature conversion with message recovery, is distributed to the system device. In a key capsule data transmission step, the key capsule data distributed by the key capsule data production and distribution step is transmitted to the system device by a user device. In a key recovery step, key capsule data transmitted by the key capsule data transmission step is received, and secret information is recovered from the key capsule data using the verification key distributed by the verification key distribution step.
Using the above processing structure, a system device can perform machine authentication and encrypted communication with all of the user devices, without needing to store unique secret information and linked user device IDs. Furthermore, even if the verification key of the signature verification conversion in the signature conversion with message recovery is illegally obtained by intrusion or analysis of a system device, the signing key used in the signature conversion with message recovery cannot be derived from this verification key. Therefore, an ill-intentioned third party cannot forge the key capsule data.